package heap;

import java.util.*;

/**
 * 基于完全二叉树的二叉堆
 * 根结点从零开始
 */
public class MaxHeap {
    List<Integer> data;

    /**
     * 默认创建大小为10的堆
     */
    public MaxHeap() {
        this(10);
    }

    /**
     * 创建指定大小的堆
     * @param len
     */
    public MaxHeap(int len) {
        data = new ArrayList<>(len);
    }

    /**
     * 将数组arr转化为最大堆
     * @param arr
     */
    public MaxHeap(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        data = new ArrayList<>();
        for (int num : arr) {
            data.add(num);
        }
        // 从最后一个非叶子节点开始，对每个非叶子节点做下沉操作
        int k = (data.size() - 1 - 1) >>1; // 最后一个非叶子节点的编号
        while (k >= 0) {
            siftDown(k);
            k --;
        }
    }

    /**
     * 判断堆是否为空
     * @return
     */
    public boolean isEmpty() {
        return data.size() == 0;
    }

    /**
     * 返回k的父结点编号
     * @param k
     * @return
     */
    public int parent(int k) {
        return (k - 1) >> 1;
    }

    /**
     * 返回左孩子的编号
     * @param k
     * @return
     */
    public int leftChild(int k) {
        return (k << 1) + 1;
    }

    /**
     * 返回右孩子的编号
     * @param k
     * @return
     */
    public int rightChild(int k) {
        return (k << 1) + 2;
    }

    /**
     * 向堆中添加值为val的元素
     * @param val
     */
    public void add(int val) {
        // 先将元素添加至末尾
        data.add(val);
        // 对元素进行上浮操作
        siftUp(data.size() - 1);
    }

    /**
     * 元素的上浮操作
     * @param k
     */
    public void siftUp(int k) {
        while (k > 0 && data.get(k) > data.get(parent(k))) {
            swap(k, parent(k));
            k = parent(k);
        }
    }

    /**
     * 交换两元素位置
     * @param k1
     * @param k2
     */
    public void swap(int k1, int k2) {
        int tmp = data.get(k1);
        data.set(k1, data.get(k2));
        data.set(k2, tmp);
    }

    /**
     * 取出堆中最大值
     * @return
     */
    public int extraMax() {
        if (isEmpty()) {
            throw new NoSuchElementException("堆为空！");
        }
        int ret = data.get(0);
        // 将最后一个叶子结点顶上根结点位置然后做下沉操作
        int index = data.size() - 1;
        swap(0, index);
        data.remove(index);
        siftDown(0);
        return ret;
    }

    /**
     * 显示最大值
     * @return
     */
    public int peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("堆为空！");
        }
        return data.get(0);
    }

    /**
     * 元素的下沉操作
     * @param k
     */
    public void siftDown(int k) {
        // 存在子树
        while (leftChild(k) < data.size()) {
            int j = leftChild(k);
            // 判断是否存在右树且右树的值大于左树
            if (j + 1 < data.size() && data.get(j) < data.get(j + 1)) {
                j = j + 1;
            }
            if (data.get(j) > data.get(k)) {
                swap(j, k);
                k = j;
            } else {
                return;
            }
        }
    }

    public String toString() {
        return data.toString();
    }
}


class Main {
    public static void main(String[] args) {
        int[] arr = new int[] {12, 13, 14, 15, 11, 10, 25, 31, 28, 62};
        MaxHeap maxHeap = new MaxHeap(arr);
        System.out.println(maxHeap.extraMax());
//        maxHeap.add(53);
//        System.out.println(maxHeap);
//        Queue<Integer> queue = new PriorityQueue<>();
//        queue.offer(1);
//        queue.offer(3);
//        queue.offer(2);
//        queue.offer(4);
//        queue.offer(5);
//        queue.offer(6);
//        List<Integer> l = new ArrayList<Integer>(queue);
//        System.out.println(Arrays.toString(l.toArray()));
    }
}
